/*
 * @lc app=leetcode.cn id=47 lang=javascript
 *
 * [47] 全排列 II
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

// 全排列nums， 放入临时数组temp，达到长度时放入ret
function unique(nums, ret, temp, len){
  if(temp.length === len) ret.push([...temp]);
  for (let i = 0; i < nums.length; i++) {
    // 因为小递归中删除了nums[i],所以此条件只会在大循环中起作用
    if(nums[i] === nums[i - 1]) continue;

    // 先选择一个元素放入数组
    temp.push(nums[i]);
    // 删除已放入元素
    nums.splice(i, 1);
    // 递归剩余元素，完成后则会生成一个结果， 小递归
    unique(nums, ret, temp, len);

    /** 回溯 */
    // 递归剩余元素之后生成一个结果后，进行下一个结果的生成， 大循环
    // 复原nums和temp，以进行第二个大循环
    nums.splice(i, 0 , temp.pop());
  }
} 
var permuteUnique = function(nums) {
  let ret = [];
  let temp = [];
  // 记录数组长度，不可在回调中取length
  let len = nums.length; 
  nums.sort((a, b)=> a - b);
  unique(nums, ret, temp, len);
  return ret;
};
// @lc code=end

